//二分查找法，在有序的数组arr中，查找target
//如果找到相应的target，返回索引值
//如果没有找到返回-1

function binarySearch1(arr, target) {
  let len = arr.length;
  //在arr[left...right]中查找target
  let left = 0, right = len - 1;
  while (left <= right) {
    //let mid = parseInt((left + right) / 2)
    let mid = left + parseInt((right - left) / 2)
    if (arr[mid] === target) {
      return mid
    } else if (target < arr[mid]) {
      //在arr[left...mid-1]中查找target
      right = mid - 1;
    } else {
      //在arr[mid+1...right]中查找target
      left = mid + 1
    }
  }
  return -1;
}

//递归的二分查找
function binarySearch2(arr, target) {
  let len = arr.length - 1;
  __binarySearch2(arr, target, 0, len)
}

function __binarySearch2(arr, target, left, right) {
  if (left > right) {
    return -1
  }
  let mid = left + parseInt((right - left) / 2)
  if (arr[mid] === target) {
    return mid
  } else if (target < arr[mid]) {
    return __binarySearch2(arr, target, left, mid - 1)
  } else {
    return __binarySearch2(arr, target, mid + 1, right)
  }
}